
# 279.完全平方数

def numSquares(n):
    """
    :type n: int
    :rtype: int
    """
    pingfang = []
    for i in range(0 ,100):
        pingfang.append(i*i)
    dp = [9999] *(n+1)
    dp[0] = 0
    for i in range(1,n+1):
        for j in range(0 ,len(pingfang)):
            if i>= pingfang[j]:
                dp[i] = min(dp[i - pingfang[j]] + 1, dp[i])
            else:
                break
    print(dp)
    return dp[n]


if __name__ == "__main__":
    n = 12
    print(numSquares(n))